package leetcode.editor.cn;
//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 6280 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution28 {
    public String longestPalindrome(String s) {
        // 假设以当前节点为回文字符串的中心
        // 分有两种情况，奇数个数、偶数个数
        String longestPalindrome = "";
        String longestPalindromeTemp = "";
        String palindromeCardinal = "";
        String palindromeEven = "";
        for (int i = 0; i < s.length(); i++) {
            palindromeCardinal = getPalindrome(i, i, s);
            palindromeEven = getPalindrome(i, i + 1, s);
            longestPalindromeTemp = palindromeCardinal.length() > palindromeEven.length() ? palindromeCardinal : palindromeEven;
            longestPalindrome = longestPalindrome.length() > longestPalindromeTemp.length() ? longestPalindrome : longestPalindromeTemp;
        }
        return longestPalindrome;
    }

    private String getPalindrome(int i, int j, String s) {
        while (i >= 0 && j < s.length()) {
            if (s.charAt(i) != s.charAt(j)) {
                break;
            }
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
